We provide almost-linear time algorithms for computing various fundamental quantities associated with random walks on directed graphs, including the stationary distribution, personalized PageRank vectors, hitting times between vertices, and escape probabilities. Previous algorithms for these problems either invoke a general purpose linear system solver or depend polynomially on condition number related quantities such as mixing time or restart probabilities.
Our result is based up several tools that may provide useful for studies into directed spectral graph theory, including: (1) a reduction from solving linear systems in arbitrary strongly connected directed graphs to Eulerian graphs; (2) spectral approximations of directed Eulerian graphs and algorithms for producing such sparse approximations; (3) approximate squaring / Gaussian elimination on Laplacians of directed graphs.
This talk is based on https://arxiv.org/abs/1608.03270, https://arxiv.org/abs/1611.00755, and works in progress. They are joint with Michael B. Cohen, Jon Kelner, Rasmus Kyng, John Peebles, Anup B. Rao, Aaron Sidford, and Adrian Vladu.
.